Leonardo được gọi vào đội tuyển quốc gia lần đầu vào năm 1990.

Anh là sự lựa chọn số 1 ở vị trí hậu vệ trái World Cup 1994, sau khi tài năng trẻ Roberto Carlos thi đấu mờ nhạt và thất vọng. Anh chơi rất tốt ở 3 trận đầu tiên, song bị treo giò bốn trận sau đó sau hành vi thô bạo với cầu thủ đội tuyển Mỹ, Tab Ramos khiến anh này vỡ nát xương gò má. Cầu thủ này sau đó phải nằm viện hơn 3 tháng. Đây cũng là án treo giò dài thứ nhì trong lịch sử World Cup sau trường hợp treo giò 8 trận đối với Mauro Tassotti làm gãy mũi Luis Enrique ở cùng giải đấu. "Tôi có một cảm giác lẫn lộn, mừng vì đội tuyển đã giành thắng lợi và không vui khi mình phải ngồi ngoài nhìn đồng đội thi đấu."

Giải đấu lớn thứ hai Leonardo tham gia là Copa America 1995. Tuy nhiên Brazil thi đấu không thành công

Năm 1997, anh được giao chiếc áo số 10: anh là nhạc trưởng của đội tuyển Brazil vô địch ở Copa America 1997 cùng với những danh thủ khác đương thời như Cafu, Ronaldo, Romário, Dunga, Cláudio Taffarel, Juninho Paulista và Roberto Carlos.

Leonardo cũng tham gia Confederations Cup 1997 và giúp Brazil vô địch sau khi thắng đội tuyển Úc 6-0 ở chung kết.

Leonardo chơi cả bảy trận ở World Cup 1998, giải đấu mà Brazil là hạt giống số 1 và thể hiện một lối chơi hết sức thuyết phục. Tuy nhiên, họ lại dừng bước ở trận chung kết trước đội tuyển Pháp.

Lần cuối anh được gọi vào đội tuyển Brazil là vào vòng loại World Cup 2002 vào tháng 9 năm 2001. Cùng năm đó, Leonardo tuyên bố giã từ sự nghiệp quốc tế.